
#include <stdio.h>  
#include <string.h>  
  
// 计算KMP算法的next数组  
void computeLPSArray(char *pat, int M, int *lps) {  
    int len = 0;   
    int i = 1;  
    lps[0] = 0;   
  
    while (i < M) {  
        if (pat[i] == pat[len]) {  
            len++;  
            lps[i] = len;  
            i++;  
        } else {  
            if (len != 0) {  
                len = lps[len - 1];  
            } else {  
                lps[i] = len;  
                i++;  
            }  
        }  
    }  
}  
  
// KMP算法实现字符串匹配，返回子串在主串中的不重叠出现次数  
int KMPSearch(char *pat, char *txt) {  
    int M = strlen(pat);  
    int N = strlen(txt);  
    int lps[M];  
    int j = 0;   
    int count = 0;   
  
    computeLPSArray(pat, M, lps);  
    int i = 0;   
    while (i < N) {  
        if (pat[j] == txt[i]) {  
            j++;  
            i++;  
        }  
        if (j == M) {  
            count++;  
            j = lps[j - 1];  
        } else if (i < N && pat[j] != txt[i]) {  
            if (j != 0) {  
                j = lps[j - 1];  
            } else {  
                i++;  
            }  
        }  
    }  
    return count;  
}  
  
int main() {  
    char txt[] = "ABABDABACDABABCABAB";  // 主串  
    char pat[] = "ABABCABAB";  // 子串  
    int count = KMPSearch(pat, txt);  // 使用KMP算法查找子串在主串中的不重叠出现次数  
    printf("子串在主串中不重叠出现的次数: %d\n", count);  // 输出结果  
    return 0;  
}
